Diseño de manipuladores basado en métodos iterativos e índices de desempeño.

Tesis (Maestría en Ciencias de la Ingeniería Eléctrica con orientación en Control Automático) UANL, 2014.

Um estudo da fatoração incompleta LU e Cholesky como pré-condicionadores nos métodos iterativos

Neste trabalho procuramos analisar alguns métodos iterativos e os processos de aceleração na solução lineares grandes e esparsos, associando o uso de alguns pré-condicionadores, tais como os métodos de fatoração incompleta. De forma mais específica, nos detivemos no estudo deos métodos de fatoração incompleta LU, ou ILU, e o método de Cholesky incompleto. Para isso procuramos antes definir algumas especificidades sobre esses métodos, tais como, crtérios de existência, limitação. Alguns fatores analisam tais problemas e sugerem algumas técnicas de conserto, ou seja, algumas maneiras de eliminar tais falhas para que os métodos de iteração possam ser utlizados para determinar soluções mais próximas da solução real. Procedemos a uma revisão teórica de alguns dos métodos iterativos, dos pré-condicionadores. Jacobi, fatoração incompleta LU e fatoração incompleta de Cholesky e a sua associação com os métodos iterativos GMRES e Gradiente Conjugado. Utilizando os pré-condionadores associados aos métodos iterativos citados e fixando alguns parâmetros de parada, aplicamos algusn testes. Os resultados e a análise dos mesmos encontram-se neste trabalho.

Simulação de escoamentos incompressíveis empregando o método Smoothed Particle Hydrodynamics utilizando algoritmos iterativos na determinação do campo de pressões

Nesse trabalho, foi desenvolvido um simulador numérico (C/C++) para a resolução de escoamentos de fluidos newtonianos incompressíveis, baseado no método de partículas Lagrangiano, livre de malhas, Smoothed Particle Hydrodynamics (SPH). Tradicionalmente, duas estratégias são utilizadas na determinação do campo de pressões de forma a garantir-se a condição de incompressibilidade do fluido. A primeira delas é a formulação chamada Weak Compressible Smoothed Particle Hydrodynamics (WCSPH), onde uma equação de estado para um fluido quase-incompressível é utilizada na determinação do campo de pressões. A segunda, emprega o Método da Projeção e o campo de pressões é obtido mediante a resolução de uma equação de Poisson. No estudo aqui desenvolvido, propõe-se três métodos iterativos, baseados noMétodo da Projeção, para o cálculo do campo de pressões, Incompressible Smoothed Particle Hydrodynamics (ISPH). A fim de validar os métodos iterativos e o código computacional, foram simulados dois problemas unidimensionais: os escoamentos de Couette entre duas placas planas paralelas infinitas e de Poiseuille em um duto infinito e foram usadas condições de contorno do tipo periódicas e partículas fantasmas. Um problema bidimensional, o escoamento no interior de uma cavidade com a parede superior posta em movimento, também foi considerado. Na resolução deste problema foi utilizado o reposicionamento periódico de partículas e partículas fantasmas.

Implementação paralelizada de métodos de resolução de sistemas algébricos na simulação de reservatórios de gás

Desde a década de 1960, devido à pertinência para a indústria petrolífera, a simulação numérica de reservatórios de petróleo tornou-se uma ferramenta usual e uma intensa área de pesquisa. O principal objetivo da modelagem computacional e do uso de métodos numéricos, para a simulação de reservatórios de petróleo, é o de possibilitar um melhor gerenciamento do campo produtor, de maneira que haja uma maximização na recuperação de hidrocarbonetos. Este trabalho tem como objetivo principal paralelizar, empregando a interface de programação de aplicativo OpenMP (Open Multi-Processing), o método numérico utilizado na resolução do sistema algébrico resultante da discretização da equação que descreve o escoamento monofásico em um reservatório de gás, em termos da variável pressão. O conjunto de equações governantes é formado pela equação da continuidade, por uma expressão para o balanço da quantidade de movimento e por uma equação de estado. A Equação da Difusividade Hidráulica (EDH), para a variável pressão, é obtida a partir deste conjunto de equações fundamentais, sendo então discretizada pela utilização do Método de Diferenças Finitas, com a escolha por uma formulação implícita. Diferentes testes numéricos são realizados a fim de estudar a eficiência computacional das versões paralelizadas dos métodos iterativos de Jacobi, Gauss-Seidel, Sobre-relaxação Sucessiva, Gradientes Conjugados (CG), Gradiente Biconjugado (BiCG) e Gradiente Biconjugado Estabilizado (BiCGStab), visando a uma futura aplicação dos mesmos na simulação de reservatórios de gás. Ressalta-se que a presença de heterogeneidades na rocha reservatório e/ou às não-linearidades presentes na EDH para o escoamento de gás aumentam a necessidade de métodos eficientes do ponto de vista de custo computacional, como é o caso de estratégias usando OpenMP.

Paralelizações de métodos numéricos em clusters empregando as bibliotecas MPICH, DECK e Pthread

Este trabalho tem como objetivo desenvolver e empregar técnicas e estruturas de dados agrupadas visando paralelizar os métodos do subespaço de Krylov, fazendo-se uso de diversas ferramentas e abordagens. A partir dos resultados é feita uma análise comparativa de desemvpenho destas ferramentas e abordagens. As paralelizações aqui desenvolvidas foram projetadas para serem executadas em um arquitetura formada por um agregado de máquinas indepentes e multiprocessadas (Cluster), ou seja , são considerados o paralelismo e intra-nodos. Para auxiliar a programação paralela em clusters foram, e estão sendo, desenvolvidas diferentes ferramentas (bibliotecas) que visam a exploração dos dois níveis de paralelismo existentes neste tipo de arquitetura. Neste trabalho emprega-se diferentes bibliotecas de troca de mensagens e de criação de threads para a exploração do paralelismo inter-nodos e intra-nodos. As bibliotecas adotadas são o DECK e o MPICH e a Pthread. Um dos itens a serem analisados nestes trabalho é acomparação do desempenho obtido com essas bibliotecas.O outro item é a análise da influência no desemepnho quando quando tulizadas múltiplas threads no paralelismo em clusters multiprocessados. Os métodos paralelizados nesse trabalho são o Gradiente Conjugação (GC) e o Resíduo Mínmo Generalizado (GMRES), quepodem ser adotados, respectivamente, para solução de sistemas de equações lineares sintéticos positivos e definidos e não simétricas. Tais sistemas surgem da discretização, por exemplo, dos modelos da hidrodinâmica e do transporte de massa que estão sendo desenvolvidos no GMCPAD. A utilização desses métodos é justificada pelo fato de serem métodos iterativos, o que os torna adequados à solução de sistemas de equações esparsas e de grande porte. Na solução desses sistemas através desses métodos iterativos paralelizados faz-se necessário o particionamento do domínio do problema, o qual deve ser feito visando um bom balanceamento de carga e minimização das fronteiras entre os sub-domínios. A estrutura de dados desenvolvida para os métodos paralelizados nesse trabalho permite que eles sejam adotados para solução de sistemas de equações gerados a partir de qualquer tipo de particionamento, pois o formato de armazenamento de dados adotado supre qualquer tipo de dependência de dados. Além disso, nesse trabalho são adotadas duas estratégias de ordenação para as comunicações, estratégias essas que podem ser importantes quando se considera a portabilidade das paralelizações para máquinas interligadas por redes de interconexão com buffer de tamanho insuficiente para evitar a ocorrência de dealock. Os resultados obtidos nessa dissertação contribuem nos trabalhos do GMCPAD, pois as paralelizações são adotadas em aplicações que estão sendo desenvolvidas no grupo.

Métodos multigrid paralelos em malhas não estruturadas aplicados à simulação de problemas de dinâmica de fluidos computacional e transferência de calor

Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

Estudos de métodos interativos e pré-condicionadores para sistemas lineares esparsos não-simétricos

Pós-graduação em Matemática - IBILCE

Avaliação dos algoritmos de Picard-Krylov e Newton-Krylov na solução da equação de Richards

A engenharia geotécnica é uma das grandes áreas da engenharia civil que estuda a interação entre as construções realizadas pelo homem ou de fenômenos naturais com o ambiente geológico, que na grande maioria das vezes trata-se de solos parcialmente saturados. Neste sentido, o desempenho de obras como estabilização, contenção de barragens, muros de contenção, fundações e estradas estão condicionados a uma correta predição do fluxo de água no interior dos solos. Porém, como a área das regiões a serem estudas com relação à predição do fluxo de água são comumente da ordem de quilômetros quadrados, as soluções dos modelos matemáticos exigem malhas computacionais de grandes proporções, ocasionando sérias limitações associadas aos requisitos de memória computacional e tempo de processamento. A fim de contornar estas limitações, métodos numéricos eficientes devem ser empregados na solução do problema em análise. Portanto, métodos iterativos para solução de sistemas não lineares e lineares esparsos de grande porte devem ser utilizados neste tipo de aplicação. Em suma, visto a relevância do tema, esta pesquisa aproximou uma solução para a equação diferencial parcial de Richards pelo método dos volumes finitos em duas dimensões, empregando o método de Picard e Newton com maior eficiência computacional. Para tanto, foram utilizadas técnicas iterativas de resolução de sistemas lineares baseados no espaço de Krylov com matrizes pré-condicionadoras com a biblioteca numérica Portable, Extensible Toolkit for Scientific Computation (PETSc). Os resultados indicam que quando se resolve a equação de Richards considerando-se o método de PICARD-KRYLOV, não importando o modelo de avaliação do solo, a melhor combinação para resolução dos sistemas lineares é o método dos gradientes biconjugados estabilizado mais o pré-condicionador SOR. Por outro lado, quando se utiliza as equações de van Genuchten deve ser optar pela combinação do método dos gradientes conjugados em conjunto com pré-condicionador SOR. Quando se adota o método de NEWTON-KRYLOV, o método gradientes biconjugados estabilizado é o mais eficiente na resolução do sistema linear do passo de Newton, com relação ao pré-condicionador deve-se dar preferência ao bloco Jacobi. Por fim, há evidências que apontam que o método PICARD-KRYLOV pode ser mais vantajoso que o método de NEWTON-KRYLOV, quando empregados na resolução da equação diferencial parcial de Richards.

Formulação teórica dos fundamentos da otimização global topográfica com análise de desempenho e aplicações à estabilidade de fases de misturas termodinâmicas

Métodos de otimização que utilizam condições de otimalidade de primeira e/ou segunda ordem são conhecidos por serem eficientes. Comumente, esses métodos iterativos são desenvolvidos e analisados à luz da análise matemática do espaço euclidiano n-dimensional, cuja natureza é de caráter local. Consequentemente, esses métodos levam a algoritmos iterativos que executam apenas as buscas locais. Assim, a aplicação de tais algoritmos para o cálculo de minimizadores globais de uma função não linear,especialmente não-convexas e multimodais, depende fortemente da localização dos pontos de partida. O método de Otimização Global Topográfico é um algoritmo de agrupamento, que utiliza uma abordagem baseada em conceitos elementares da teoria dos grafos, a fim de gerar bons pontos de partida para os métodos de busca local, a partir de pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem dois objetivos. O primeiro é realizar uma nova abordagem sobre método de Otimização Global Topográfica, onde, pela primeira vez, seus fundamentos são formalmente descritos e suas propriedades básicas são matematicamente comprovadas. Neste contexto, propõe-se uma fórmula semi-empírica para calcular o parâmetro chave deste algoritmo de agrupamento, e, usando um método robusto e eficiente de direções viáveis por pontos-interiores, estendemos o uso do método de Otimização Global Topográfica a problemas com restrições de desigualdade. O segundo objetivo é a aplicação deste método para a análise de estabilidade de fase em misturas termodinâmicas,o qual consiste em determinar se uma dada mistura se apresenta em uma ou mais fases. A solução deste problema de otimização global é necessária para o cálculo do equilíbrio de fases, que é um problema de grande importância em processos da engenharia, como, por exemplo, na separação por destilação, em processos de extração e simulação da recuperação terciária de petróleo, entre outros. Além disso, afim de ter uma avaliação inicial do potencial dessa técnica, primeiro vamos resolver 70 problemas testes, e então comparar o desempenho do método proposto aqui com o solver MIDACO, um poderoso software recentemente introduzido no campo da otimização global.

Precondicionadores baseados na aproximação da inversa.

Neste trabalho de dissertação apresentaremos uma classe de precondicionadores baseados na aproximação esparsa da inversa da matriz de coecientes, para a resolução de sistemas lineares esparsos de grandes portes através de métodos iterativos, mais especificamente métodos de Krylov. Para que um método de Krylov seja eficiente é extremamente necessário o uso de precondicionadores. No contexto atual, onde computadores de arquitetura híbrida são cada vez mais comuns temos uma demanda cada vez maior por precondicionadores paralelizáveis. Os métodos de inversa aproximada que serão descritos possuem aplicação paralela, pois so dependem de uma operação de produto matriz-vetor, que é altamente paralelizável. Além disso, alguns dos métodos também podem ser construídos em paralelo. A ideia principal é apresentar uma alternativa aos tradicionais precondicionadores que utilizam aproximações dos fatores LU, que apesar de robustos são de difícil paralelização.

Otimização global topográfica aplicada a problemas de otimização com restrições de igualdade e desigualdade

Os métodos de otimização que adotam condições de otimalidade de primeira e/ou segunda ordem são eficientes e normalmente esses métodos iterativos são desenvolvidos e analisados através da análise matemática do espaço euclidiano n-dimensional, o qual tem caráter local. Esses métodos levam a algoritmos iterativos que são usados para o cálculo de minimizadores globais de uma função não linear, principalmente não-convexas e multimodais, dependendo da posição dos pontos de partida. Método de Otimização Global Topográfico é um algoritmo de agrupamento, o qual é fundamentado nos conceitos elementares da teoria dos grafos, com a finalidade de gerar bons pontos de partida para os métodos de busca local, com base nos pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem como objetivo a aplicação do método de Otimização Global Topográfica junto com um método robusto e eficaz de direções viáveis por pontos-interiores a problemas de otimização que tem restrições de igualdade e/ou desigualdade lineares e/ou não lineares, que constituem conjuntos viáveis com interiores não vazios. Para cada um destes problemas, é representado também um hiper-retângulo compreendendo cada conjunto viável, onde os pontos amostrais são gerados.

Análise estática e dinâmica, linear e não-linear geométrica, através de elementos hexaédricos de oito nós com um ponto de integração

Para a análise estática e dinâmica, linear e não-linear de placas, cascas e vigas, implementa-se neste trabalho o elemento hexaédrico com integração reduzida, livre de travamento volumétrico e travamento de cisalhamento e que não apresenta modos espúrios. Na formulação do elemento, utiliza-se apenas um ponto de integração. Desta forma, a matriz de rigidez é dada de forma explícita e o tempo computacional é significativamente reduzido, especialmente em análise não-linear. Os modos espúrios são suprimidos através de um procedimento de estabilização que não exige parâmetros especificados pelo usuário. Para evitar o travamento de cisalhamento, desenvolve-se o vetor de deformações num sistema co-rotacional e remove-se certos termos não constantes nas componentes de deformações de cisalhamento. O travamento volumétrico é resolvido fazendo-se com que a parte dilatacional (esférica) da matriz gradiente seja avaliada apenas no ponto central do elemento. Como a eliminação do travamento de cisalhamento depende de uma abordagem no sistema local, emprega-se um procedimento co-rotacional para obter o incremento de deformação no sistema local e atualizar os vetores de tensões e forças internas na análise não-linear Para a solução das equações de equilíbrio na análise estática, utilizam-se métodos diretos baseados na eliminação de Gauss ou métodos iterativos de Gradientes Conjugados Precondicionado elemento-por-elemento (EBE). Para a análise dinâmica, as equações de equilíbrio são integradas através do método explícito de Taylor-Galerkin ou do método implícito de Newmark. Através de exemplos numéricos demonstra-se a eficiência e o potencial do elemento tridimensional na análise de casca, placas e vigas submetidas a grandes deslocamentos e grande rotações. Os resultados são comparados com trabalhos que utilizam elementos clássicos de placa e casca.

Medidas de coerência para análise de velocidade na migração em tempo

Métodos iterativos para a análise de velocidade com migração dependem das funções objetivo medirem a horizontalização dos eventos de reflexão em famílias de ponto imagem comum (CIG). A migração em tempo é um método simples de imageamento para avaliar essas funções objetivo. Usando migração em tempo, estudamos a influência da função objetivo nos resultados da análise de velocidade com migração. Propomos duas novas funções objetivo para a análise velocidade com migração: Semblance Diferencial Estendido e o produto do Semblance Clássico com o Semblance Diferencial Estendido. Experimentos numéricos, utilizando os dados Marmousoft, mostram a eficácia das novas funções objetivo em estimar modelos velocidade produzindo eventos horizontalmente alinhados nas famílias de ponto imagem comum.

SPECT (Single photon emission tomography): Gama câmara, reconstrução tomográfica e características funcional

The SPECT (Single Photon Emission Computed Tomography) systems are part of a medical image acquisition technology which has been outstanding, because the resultant images are functional images complementary to those that give anatomic information, such as X-Ray CT, presenting a high diagnostic value. These equipments acquire, in a non-invasive way, images from the interior of the human body through tomographic mapping of radioactive material administered to the patient. The SPECT systems are based on the Gamma Camera detection system, and one of them being set on a rotational gantry is enough to obtain the necessary data for a tomographic image. The images obtained from the SPECT system consist in a group of flat images that describe the radioactive distribution on the patient. The trans-axial cuts are obtained from the tomographic reconstruction techniques. There are analytic and iterative methods to obtain the tomographic reconstruction. The analytic methods are based on the Fourier Cut Theorem (FCT), while the iterative methods search for numeric solutions to solve the equations from the projections. Within the analytic methods, the filtered backprojection (FBP) method maybe is the simplest of all the tomographic reconstruction techniques. This paper's goal is to present the operation of the SPECT system, the Gamma Camera detection system, some tomographic reconstruction techniques and the requisites for the implementation of this system in a Nuclear Medicine service

Método multigrid algébrico: reutilização das estruturas multigrid no transporte de contaminantes

A necessidade de obter solução de grandes sistemas lineares resultantes de processos de discretização de equações diferenciais parciais provenientes da modelagem de diferentes fenômenos físicos conduz à busca de técnicas numéricas escaláveis. Métodos multigrid são classificados como algoritmos escaláveis.Um estimador de erros deve estar associado à solução numérica do problema discreto de modo a propiciar a adequada avaliação da solução obtida pelo processo de aproximação. Nesse contexto, a presente tese caracteriza-se pela proposta de reutilização das estruturas matriciais hierárquicas de operadores de transferência e restrição dos métodos multigrid algébricos para acelerar o tempo de solução dos sistemas lineares associados à equação do transporte de contaminantes em meio poroso saturado. Adicionalmente, caracteriza-se pela implementação das estimativas residuais para os problemas que envolvem dados constantes ou não constantes, os regimes de pequena ou grande advecção e pela proposta de utilização das estimativas residuais associadas ao termo de fonte e à condição inicial para construir procedimentos adaptativos para os dados do problema. O desenvolvimento dos códigos do método de elementos finitos, do estimador residual e dos procedimentos adaptativos foram baseados no projeto FEniCS, utilizando a linguagem de programação PYTHONR e desenvolvidos na plataforma Eclipse. A implementação dos métodos multigrid algébricos com reutilização considera a biblioteca PyAMG. Baseado na reutilização das estruturas hierárquicas, os métodos multigrid com reutilização com parâmetro fixo e automática são propostos, e esses conceitos são estendidos para os métodos iterativos não-estacionários tais como GMRES e BICGSTAB. Os resultados numéricos mostraram que o estimador residual captura o comportamento do erro real da solução numérica, e fornece algoritmos adaptativos para os dados cuja malha retornada produz uma solução numérica similar à uma malha uniforme com mais elementos. Adicionalmente, os métodos com reutilização são mais rápidos que os métodos que não empregam o processo de reutilização de estruturas. Além disso, a eficiência dos métodos com reutilização também pode ser observada na solução do problema auxiliar, o qual é necessário para obtenção das estimativas residuais para o regime de grande advecção. Esses resultados englobam tanto os métodos multigrid algébricos do tipo SA quanto os métodos pré-condicionados por métodos multigrid algébrico SA, e envolvem o transporte de contaminantes em regime de pequena e grande advecção, malhas estruturadas e não estruturadas, problemas bidimensionais, problemas tridimensionais e domínios com diferentes escalas.